1. Field of the Invention
The present invention relates to search engines for rapid text or data search from a memory or storage device. In particular, the present invention provides the capability for parallel examination of a plurality of data bytes with a predetermined character string. The comparison is conducted without required reference to position in the string and is insensitive to word boundaries through the use of a feed forward of comparison hits creating a sequence of successive hits for a successful compare to the search string. Addition of masking characters, skip characters and wild-card characters as control elements for the detection sequence provides additional flexibility for the search engine.
2. Prior Art
As database size has increased and the requirements for searching for specific data patterns, whether in the form of character strings or binary data, the need for rapid search capability has increased. Exemplary techniques for searching character strings have typically relied on a serial assessment of a target string of characters, comparing a serial flow of data to the first character in the string and, upon receiving a positive compare, advancing to the second character to compare the next serial character in the incoming data. If a positive compare on the second character is not received, the search retreats back to the first character continuing the serial search.
Various means to perform some portions of the search in parallel have been disclosed in the prior art. U.S. Pat. No. 4,053,871 to Vidalin, et al. discloses a method and system for iterative and simultaneous comparison of data with a group of reference data items. However, the Vidalin system is specifically restricted to a particular format of data entry to allow parallel comparison of sequential data appearing in each element of the format. For highly structured databases, the Vidalin device provides the necessary enhancement, however, the system is inoperable for unstructured data.
U.S. Pat. No. 4,433,392 to Beaven discloses a system less sensitive to data structure, however, while comparisons are conducted in parallel in the Beaven device, data transfer is conducted serially thereby severely limiting the search speed. A similar device disclosed in U.S. Pat. No. 4,847,877 to Besseyre enhances speed of detection during serial bit transmission by detecting data in frames comprising more than a single element of the search pattern thereby allowing cessation of search on a frame once a dissimilarity has been identified. While the Besseyre approach improves on the overall speed of the Beaven device, serial transmission of the data to be searched ultimately limits the search speed.
U.S. Pat. No. 4,550,436 to Freeman et al. discloses yet another device which operates to provide a parallel comparison of incoming data with a serially supplied search string, again providing termination of the search upon failure to obtain a second match after a first match has been obtained.
The present invention overcomes the shortcomings of the prior art by providing a true parallel comparison of both the search string and data retrieved from the memory or storage device while maintaining flexibility for insertion of masking or skipping of special characters and examination for wild-card characters to accommodate various potential forms of the data being searched. The present invention provides for up to four skip characters thereby overcoming the issues of word searching with hyphenation.